package shuati.jianxinhuyu;

/**
 * @author : LdLtd
 * @Date : 2024/4/13
 * @Description:
 * 如果一个字符串，组成这个字符串的每一种字符出现次数均为偶数，则这个字符串称为“偶次串”
 * 给定一个字符串S，求S的子串中最长的“偶次串”的长度。举例:
 * 字符串"abcbcde"的子串中，最长的“偶次串”为“bcbc”，长度为4
 * 题目保证输入的字符串S中仅有abcdefg这7种字符，字符串长度<=64K。
 */
public class oucichuan {
    public static void main(String[] args) {
        System.out.println(longestEvenString("abababababcbcbcbcde"));
    }
    public static int longestEvenString(String s){
        int n=s.length();
        //dp[i] 表示字符串 s 的前 i 个字符组成的子串中，每种字符出现的次数的奇偶性的状态编码
        //如 1001010 表示第 b,d,g 字符出现了奇数次，其他字符出现了偶数次
        int [] dp=new int[n+1];
        int res=0;
        for (int i = 1; i <= n; i++) {
            // 1^1=0  0^1=1 1^0=1  0^0=0,基数异或偶数为1，偶数异或偶数为0
            //为0的时候表示是偶数
            dp[i]=dp[i-1]^(1<<(s.charAt(i-1)-'a'));
                //找到前面的一个位置，使得dp[i]和dp[k]异或的结果为0
                for (int k = 0; k <i; k++) {
                    if((dp[i]^dp[k])==0){
                        res=Math.max(res,i-k);
                        break;
                    }
                }
        }
        return res;
    }
}
